package com.shm.leetcode;

import java.util.Arrays;

/**
 * 475. 供暖器
 * 冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
 *
 * 在加热器的加热半径范围内的每个房屋都可以获得供暖。
 *
 * 现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
 *
 * 说明：所有供暖器都遵循你的半径标准，加热的半径也一样。
 *
 *
 *
 * 示例 1:
 *
 * 输入: houses = [1,2,3], heaters = [2]
 * 输出: 1
 * 解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
 * 示例 2:
 *
 * 输入: houses = [1,2,3,4], heaters = [1,4]
 * 输出: 1
 * 解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。
 * 示例 3：
 *
 * 输入：houses = [1,5], heaters = [2]
 * 输出：3
 *
 *
 * 提示：
 *
 * 1 <= houses.length, heaters.length <= 3 * 104
 * 1 <= houses[i], heaters[i] <= 109
 * @author SHM
 */
public class FindRadius {
    /**
     * 方法一：排序 + 二分查找
     * 思路和算法
     *
     * 为了使供暖器可以覆盖所有房屋且供暖器的加热半径最小，对于每个房屋，应该选择离该房屋最近的供暖器覆盖该房屋，最近的供暖器和房屋的距离即为该房屋需要的供暖器的最小加热半径。所有房屋需要的供暖器的最小加热半径中的最大值即为可以覆盖所有房屋的最小加热半径。
     *
     * 为了得到距离每个房屋最近的供暖器，可以将供暖器数组 \textit{heaters}heaters 排序，然后通过二分查找得到距离最近的供暖器。
     *
     * 具体而言，对于每个房屋 \textit{house}house，需要在有序数组 \textit{heaters}heaters 中找到最大的下标 ii，使得 \textit{heaters}[i] \le \textit{house}heaters[i]≤house，特别地，当 \textit{heaters}[0] > \textit{house}heaters[0]>house 时，i = -1i=−1。在得到下标 ii 之后，令 j = i + 1j=i+1，则 jj 是满足 \textit{heaters}[j] > \textit{house}heaters[j]>house 的最小下标。特别地，当 \textit{heaters}[n - 1] \le \textit{house}heaters[n−1]≤house 时，j = nj=n，其中 nn 是数组 \textit{heaters}heaters 的长度。
     *
     * 得到下标 ii 和 jj 之后，离房屋 \textit{house}house 最近的供暖器为 \textit{heaters}[i]heaters[i] 或 \textit{heaters}[j]heaters[j]，分别计算这两个供暖器和房屋 \textit{house}house 的距离，其中的最小值即为该房屋需要的供暖器的最小加热半径。对于 i = -1i=−1 或 j = nj=n 的下标越界情况，只要将对应的距离设为 +\infty+∞ 即可。
     *
     * 复杂度分析
     *
     * 时间复杂度：O((n + m) \log n)O((n+m)logn)，其中 mm 是数组 \textit{houses}houses 的长度，nn 是数组 \textit{heaters}heaters 的长度。
     * 对数组 \textit{heaters}heaters 排序需要 O(n \log n)O(nlogn) 的时间。
     * 使用二分查找对每个房屋寻找距离最近的供暖器，每次二分查找需要 O(\log n)O(logn) 的时间，有 mm 个房屋，因此需要 O(m \log n)O(mlogn) 的时间。
     * 总时间复杂度是 O((n + m) \log n)O((n+m)logn)。
     *
     * 空间复杂度：O(\log n)O(logn)，其中 nn 是数组 \textit{heaters}heaters 的长度。空间复杂度主要取决于排序所需要的空间。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/heaters/solution/gong-nuan-qi-by-leetcode-solution-rwui/
     * @param houses
     * @param heaters
     * @return
     */
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int ans = 0;
        for (int house : houses) {
            int i = binarySearch(heaters,house);
            int j = i+1;
            int leftDistance = i<0?Integer.MAX_VALUE:house-heaters[i];
            int rightDistance = j>heaters.length?Integer.MAX_VALUE:heaters[j]-house;
            int curDistance = Math.min(leftDistance,rightDistance);
            ans = Math.max(ans,curDistance);
        }
        return ans;
    }

    public int binarySearch(int[] num,int target){
        int left = 0,right = num.length-1;
        if (num[left]>target){
            return -1;
        }
        while (left<right){
            int mid = left+(right-left+1)/2;
            if (num[mid]>target){
                right=mid-1;
            }else {
                left=mid;
            }
        }
        return left;
    }
}
